Most general purpose digital computing machines have been constructed through a central system organization in which the main storage is connected to outlying secondary storage such as disks, tapes, drums, etc. on one side and to the CPU on the other. Main storage itself often remains an essentially undivided bulk storage entity to the hardware, although to software in a multiprogramming environment it may be divided into regions or partitions in which programs are located during the executing period. It has been suggested that main storage should be hardware divided into hierarchical levels in which a small, fast access level would be directly connected to the central processing unit and larger, slower access backing levels successively connected to the first high speed level. U.S. Pat. No. 3,218,611 to Kilburn et al., assigned to the assignee of the present invention, is directed toward a hierarchical organization with directory registers for keeping track of where particular data is stored.
The need for hierarchies in main storage results from the need for memory to keep pace with CPU speeds while, at the same time, providing the large physical memory size demanded by the need to handle large problems. Unfortunately, large size and fast access speed are conflicting goals in the design of main storage, for as memory capacity increases, a larger physical package results which, in turn, causes an increase in transmission times. Thus, the hierarchical arrangement of main storage appears desirable to provide matching speeds between the main storage and the CPU.
In an article entitled "Concepts for Buffer Storage," C. J. Conti, IEEE Computer Group News, March 1969, the author describes four design variations in providing an hierarchicl arrangement. One of these arrangements has been implemented on System/360 Model 85 and is described as dividing main memory into sectors of 1,024 bytes and mapping these sectors into a fast acting buffer with a tag address associated with each sector. The sector is described as further divided into 64 byte blocks which, due to the design of System/360 Model 85, is close to the optimal transfer size of information for that particular computer. The addressing of such a scheme is provided by three low order bits to define a byte within a word, the next 3 bits to define the word, a 4 bit identifier for the block and a 14 bit identifier for the sector.
The author also describes three other mapping techniques and identifies the "set associative buffer" technique as the best of any of the four presented. In this technique both backing storage and buffer storage are divided into blocks with each block of buffer storage having a tag associated with it. Blocks in buffer storage are grouped into sets with, for example, two blocks per set. If buffer storage is large enough to contain 64 sets and if main memory is large enough to contain 16,384 blocks, then each set in the buffer storage can be associated with a specific 256 blocks in backing storage. At any instant of time, any of those 256 blocks may be in either of the two block positions in that particular buffer set. Thus by inspecting two tags in the set, it can be determined which of the 256 blocks are in the buffer. The effective address in this arrangement provides a low order 3 bits to identify the byte, the next three low order bits to identify the word, and the remaining 18 bits to identify the set and the tag.
In addition to selecting the type of mapping which must be built into the machinery to transfer information from a large capacity storage into a smaller storage, a replacement algorithm must also be provided; that is, when information in high speed storage is to be replaced by other information, the blocks must be replaced through random selection, by least recently used, or by some other replacement technique. An example of a replacement system may be found in U.S. Pat. No. 3,541,529, assigned to the assignee of the present invention.
Finally, a storage philosophy must be selected to define the manner in which information is to be stored. For example, if a Store-In-Buffer (SIB) philosophy is selected and if a target block is present in the first high speed buffer level of storage, the store is made with no other action. However, if the target block is not present at the first level, a pull is generated to succeeding levels in order to obtain the block. Pulls are propagated until the target block is found and then it is brought forward until it reaches the first level of storage where the store can then be made from the CPU to the buffer.
If a Store-Wherever (STW) philosophy is selected and if the target block is not found in the high speed buffer, a search is made to successively higher levels until the block is found. At that point, the CPU stores directly into the block at that level. There is no bringing the block upwardly to level 1 prior to the store.
A third storage philosophy may be the Store-Through (STH) technique where, when a block is present in the high speed level, the store is made there and then is also propagated to the next lower levels. Hence, if a trail of copies has been left in the various levels of storage, each level will be updated since the store will be propagated all the way down. If the block is not present in the high speed level, the store request is propagated to the next lower level and so on until the block is found. The store is made directly to the level at which the block is first found and from that point, a propagation is made through succeeding levels to update a trail of copies.
Thus, the performance of a multi-level storage hierarchy is responsive to many inter-dependent parameters at every level. These parameters include block size, number of blocks, the replacement algorithm, the storage philosophy, the ratio of access time, etc., but performance depends especially on the sequence of addresses generated during the performance of a job mix. If the sequence of generated addresses continually uses blocks of data already mapped into the high speed buffer, performance will be high. However, it will be degraded as it becomes necessary to obtain new blocks of information from lower levels of storage and map them into the high speed level in order to execute the job mix. The traditional prior art method of evaluating a hierarchy proposal is to drive a computer model of the hierarchy with an address sequence also called an address trace or trace tape. The disadvantages of this method lie principally in the difficulty of obtaining representative of undistorted address traces since virtually any program will become compute bound by tracing its execution. Thus, even though a particular job mix may be well balanced in terms of the I/O and CPU activities, when all jobs are traced, the environment becomes compute bound and it is impossible to obtain a realistic trace of the job stream. Additionally, some operations are timing sensitive and the imposition of a trace into the operation destroys its timing.
Thus, it is an overall objective of the present invention to provide a mechanism for testing the performance of various storage hierarchies against an undistorted address stream without actually implementing multi-level storage hierarchies by driving a system of directories which emulates particular storage hierarchies so that their performance can be predicted from the use of a single level general purpose computer such as a System/360 Model 65. In this manner, various hierarchical designs can be examined in relation to various job streams in order to determine which design provides the best performance over a widely varying range of job mixes.